package leetcode.interviewClassics;

import leetcode.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author Cheng Jun
 * Description: 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-two-numbers-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/7/31 23:51
 */
public class addTwoNumbers2 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> q1 = new ArrayDeque<>();
        Deque<Integer> q2 = new ArrayDeque<>();
        // 先入栈，再出栈，进一标志
        while(l1 != null){
            q1.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null){
            q2.push(l2.val);
            l2 = l2.next;
        }
        int flag = 0;
        ListNode dummy = new ListNode();
        while(!q1.isEmpty() || !q2.isEmpty() || flag == 1){
            int sum = flag;
            if(!q1.isEmpty()){
                sum += q1.pop();
            }
            if(!q2.isEmpty()){
                sum += q2.pop();
            }
            // 链表的头插法，不断在链表头增加节点
            dummy.next = new ListNode(sum % 10, dummy.next);
            flag = sum / 10;
        }
        return dummy.next;
    }
}
